
//1926.迷宫中离入口最近的出口
class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        //使用BFS一层层的向外扩
        int n=maze.size(),m=maze[0].size(),step=0;
        int dx[]={0,0,1,-1};
        int dy[]={1,-1,0,0};
        queue<pair<int,int>> st;  //记录向外扩的坐标
        st.push({entrance[0],entrance[1]});
        maze[entrance[0]][entrance[1]]='+';

        while(!st.empty())
        {
            //此时st不为空,说明还可以像外扩
            int num=st.size();
            step++;     //先外扩,次数+1
            for(int i=0;i<num;i++)
            {
                int x=st.front().first,y=st.front().second;
                st.pop();
                for(int k=0;k<4;k++)
                {
                    int a=x+dx[k],b=y+dy[k];
                    if(a<0||a>=n||b<0||b>=m||maze[a][b]=='+') continue;  //不满足条件的坐标
                    if(a==0||a==n-1||b==0||b==m-1) return step;     //找到了目标位置

                    maze[a][b]='+';   //在此处就需要将矩阵坐标置为'+'防止其他位置重复加入,导致超时
                    st.push({a,b});   //将当前位置加入到队列中
                }
            }   
        }
        return -1;
    }
};